package _滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class point {
    // 双指针。三指针。左右指针。快慢指针

    // 找不到的题 去 _Armay 、 _653_两个文件里去找

    // 75:颜色分类：三指针法（荷兰国旗问题）：https://leetcode.cn/problems/sort-colors/
    // 类似的问题：将负数放左边，正数放右边，0 留中间
    public void sortColors(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int cur = 0;
        // l是 0,1 分界线，r是 1,2 分界线，cur是当前遍历指针
        // [l,r] 是最后的1所占区间
        while (cur <= r) {
            if (nums[cur] == 0) {
                swap(nums, cur++, l++);
            } else if (nums[cur] == 2) {
                swap(nums, cur, r--); // cur 不加（因为可能换过来的是0，2）
            } else {
                // cur需要保证前面的元素只有0和1
                cur++;
            }
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //    三数之和：https://leetcode.cn/problems/3sum/description/
//    固定一个数去求另外两个数
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1, r = nums.length - 1; // 左闭右闭的区间
            // 剪枝
            if (nums[i] > 0 || nums[r] < 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) l++;
                else if (sum > 0) r--;
                else {
                    list.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 不能包含重复元素
                    while (l < r && nums[l + 1] == nums[l]) l++;
                    while (l < r && nums[r - 1] == nums[r]) r--;
                }
            }
        }
        return list;
    }

    // 最接近的三数之和 https://leetcode.cn/problems/3sum-closest/
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int clostNum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(sum - target) < Math.abs(clostNum - target)) {
                    clostNum = sum;
                }
                if (sum > target) r--;
                else if (sum < target) l++;
                else return target;
            }
        }
        return clostNum;
    }

    // 移动0：
    public void moveZeroes(int[] nums) {
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[s++] = nums[i];
            }
        }
        for (int i = s; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    //    167：两数之和II：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
//    输入：numbers = [2,7,11,15], target = 9
//    输出：[1,2]
//    解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]
    public int[] twoSum2(int[] numbers, int target) {
        for (int l = 0, r = numbers.length - 1; l < r; ) {
            int sum = numbers[l] + numbers[r];
            if (sum < target)
                l++;
            else if (sum > target)
                r--;
            else return new int[]{l + 1, r + 1};
        }
        return null;
    }

    // 392：判断子序列：https://leetcode.cn/problems/is-subsequence/description/
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        int n = s.length(), m = t.length();
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

    // 287：寻找重复数：https://leetcode.cn/problems/find-the-duplicate-number/
    // 快慢指针
    public int findDuplicate(int[] nums) {
        // 其数字都在 [1, n] 范围内
        int s = 0, f = 0;
        do {
            s = nums[s];
            f = nums[nums[f]];
        } while (s != f);
        s = 0;
        while (s != f) {
            s = nums[s];
            f = nums[f];
        }
        return s;
    }

    // 202：快乐数：https://leetcode.cn/problems/happy-number/
    // 快慢指针
    public boolean isHappy(int n) {
        int s = n;
        int f = next(n);
        while (f != 1 && s != f) {
            s = next(s);
            f = next(next(f));
        }
        return f == 1;
    }

    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            sum += d * d;
        }
        return sum;
    }

    // 42：接雨水：https://leetcode.cn/problems/trapping-rain-water/
    // 用两个指针遍历、两个变量记录左右最大高度，
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;

        // 当前位置的左侧木板高度，右侧木板高度
        int lm = 0, rm = 0;
        int res = 0;
        while (l < r) {
            lm = Math.max(lm, height[l]);
            rm = Math.max(rm, height[r]);

            if (lm < rm) {
                res += lm - height[l];
                l++;
            } else {
                res += rm - height[r];
                r--;
            }
        }
        return res;
    }

    // 11：盛水最多的容器：https://leetcode.cn/problems/container-with-most-water/
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0;
        while (l < r) {
            res = Math.max(res, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) {
                l++;
            } else
                r--;
        }
        return res;
    }

    // 905： 按奇偶排序数组：https://leetcode.cn/problems/sort-array-by-parity/description/
    // 齐头并进，让r在前面探路！    l指向偶数元素
    public int[] sortArrayByParity(int[] nums) {
        int l = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] % 2 == 0) {
                // swap nums[l] 和 nums[r]
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;

                l++;
            }
        }
        return nums;
    }

    // 左右指针：l 始终指向偶数，r 始终指向奇数
    public int[] sortArrayByParityII(int[] nums) {
        int l = 0, r = nums.length - 1;

        // 找到不符合条件的数，然后交换
        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 == 1) r--;

            if (l < r) {
                swap(nums, l, r);
                l++;
                r--;
            }
        }
        return nums;
    }

    // 581：最短无序连续子数组：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/
    /*    如果一个数组是部分乱序的，那么这个子数组的最大值应该会“影响”右边；最小值应该会“影响”左边。
                从左到右找乱序中的最小值 minVal；
                从右到左找乱序中的最大值 maxVal；
                再从头找第一个大于 minVal 的位置 l；
                从尾找第一个小于 maxVal 的位置 r；
                [l, r] 就是需要排序的子数组。
    */
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        boolean flag = false;

        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) flag = true;
            if (flag) min = Math.min(min, nums[i]);
        }
        flag = false;

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) flag = true;
            if (flag) max = Math.max(max, nums[i]);
        }

        int l = 0;
        while (l < n && nums[l] <= min) l++;

        int r = n - 1;
        while (r >= 0 && nums[r] >= max) r--;

        return r > l ? r - l + 1 : 0;
    }

}
